package com.mlh.backtracking;

// 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
// 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
// 可以从网络格子中任意一个格子开始
public class 单词搜索 {
    int rowLen, colLen;
    boolean res = false;// 最终的判定结果
    char[] chars;
    boolean[][] visited;// 记录是否走过某个位置

    public boolean method1(char[][] board, String word) {
        rowLen = board.length;
        colLen = board[0].length;
        chars = word.toCharArray();
        visited = new boolean[rowLen][colLen];
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                recursion(board, 0, i, j);
                if (res) {
                    return true;
                }
            }
        }
        return false;
    }

    public void recursion(char[][] board, int index, int row, int col) {
        // 先判断字符是否相同 后判断长度是否达标
        // 这样能够保证board=[[a]] word=a 这种能够通过
        if (board[row][col] != chars[index] || res) {
            return;
        }
        if (index == chars.length - 1) {
            res = true;
            return;
        }
        visited[row][col] = true;
        int[][] directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int[] direction : directions) {
            int rowNew = row + direction[0];
            int colNew = col + direction[1];
            if (rowNew < rowLen && rowNew >= 0 && colNew >= 0 && colNew < colLen && !visited[rowNew][colNew]) {
                recursion(board, index + 1, rowNew, colNew);
            }
        }
        visited[row][col] = false;
    }

    public boolean practice(char[][] board, String word) {
        rowLen = board.length;
        colLen = board[0].length;
        visited = new boolean[rowLen][colLen];
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                recursionPractice(board, word,0, i, j);
                if (res) {
                    return true;
                }
            }
        }
        return false;
    }

    public void recursionPractice(char[][] board, String word, int index, int row, int col) {
        if (index >= word.length() || word.charAt(index) != board[row][col] || res) {
            return;
        }
        //通过前一个if判断这个字符能够匹配word中下标为index的字符，我们才继续下去
        visited[row][col] = true;
        if (index == word.length() - 1) {
            res = true;
            return;
        }
        int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        for (int i = 0; i < 4; i++) {
            int tempRow = row + directions[i][0];
            int tempCol = col + directions[i][1];
            if (tempRow < 0 || tempRow >= rowLen || tempCol < 0 || tempCol >= colLen || visited[tempRow][tempCol]) {
                continue;
            }
            recursionPractice(board, word, index + 1, tempRow, tempCol);
        }
        visited[row][col] = false;
    }
}
